package cn.fansunion.leecode.isNumber;

/**
 * 
 * 根据丑数的定义，00 和负整数一定不是丑数。
 * 
 * 当 n>0n>0 时，若 nn 是丑数，则 nn 可以写成 n = 2^a \times 3^b \times 5^cn=2 a ×3 b ×5 c 的形式，其中 a,b,ca,b,c 都是非负整数。特别地，当 a,b,ca,b,c
 * 都是 00 时，n=1n=1。
 * 
 * 为判断 nn 是否满足上述形式，可以对 nn 反复除以 2,3,52,3,5，直到 nn 不再包含质因数 2,3,52,3,5。若剩下的数等于 11，则说明 nn 不包含其他质因数，是丑数；否则，说明 nn 包含其他质因数，不是丑数。
 * 
 * https://leetcode-cn.com/problems/ugly-number/
 * @author wen.lei@brgroup.com
 *
 *         2021-12-29
 */
public class UglyNumber {

    /**
     * @param args
     */
    public static void main(String[] args) {
        UglyNumber un = new UglyNumber();
        System.out.println(un.isUglyIteration(0));
        System.out.println(un.isUglyIteration(1));
        System.out.println(un.isUglyIteration(6));
        System.out.println(un.isUglyIteration(8));
        System.out.println(un.isUglyIteration(14));
        System.out.println(un.isUglyIteration(28));
        System.out.println(un.isUglyRecursive(1));
        System.out.println(un.isUglyRecursive(6));
        System.out.println(un.isUglyRecursive(8));
        System.out.println(un.isUglyRecursive(14));
        System.out.println(un.isUglyRecursive(28));
    }

    /**
     * leecode,官方解法，比较简洁 https://leetcode-cn.com/problems/ugly-number/solution/chou-shu-by-leetcode-solution-fazd/
     * 
     * @param n
     * @return
     */
    public  boolean isUgly(int n) {
        if (n <= 0) {
            return false;
        }
        int[] factors = {2, 3, 5};
        for (int factor : factors) {
            while (n % factor == 0) {
                n /= factor;
            }
        }
        return n == 1;
    }

    /**
     * 迭代写法（不改变输入值n），同isUgly本质相同
     * 
     * @param n
     * @return
     */
    public  boolean isUglyIteration(int n) {
        int n2 = n;
        while (n2 >= 2 && n2 % 2 == 0) {
            n2 = n2 / 2;
        }
        int n3 = n2;
        while (n3 >= 3 && n3 % 3 == 0) {
            n3 = n3 / 3;
        }
        int n5 = n3;
        while (n5 >= 5 && n5 % 5 == 0) {
            n5 = n5 / 5;
        }
        return n5 == 1;
    }

    /**
     * 递归写法（不改变输入值n）
     * 
     * @param n
     * @return
     */
    public  boolean isUglyRecursive(int n) {
        int n2 = n;
        if (n2 >= 2 && n2 % 2 == 0) {
            n2 = n2 / 2;
            return isUglyRecursive(n2);
        }
        int n3 = n2;
        if (n2 >= 3 && n3 % 3 == 0) {
            n3 = n3 / 3;
            return isUglyRecursive(n3);
        }
        int n5 = n3;
        if (n2 >= 5 && n5 % 5 == 0) {
            n5 = n5 / 5;
            return isUglyRecursive(n5);
        }
        return n5 == 1;
    }

}
